Méthodes basées sur la programmation dynamique

Dans le cadre de l'apprentissage par renforcement, l'utilisation de méthodes de programmation dynamiques permet de calculer les solutions des fonctions de valeurs d'états et d'actions optimales. Cela nous permettra de déterminer par la suite la stratégie que l'agent doit suivre.

Ces méthodes fonctionnent lorsque:

• Le MDP possède un nombre fini et restreint d'états
• Le modèle de l'environnement est parfaitement connu

Nous allons étudier deux algorithmes qui sont:

• L'algorithme par itération des stratégies (Policy Iteration). Cet algorithme comprend deux étapes principales:

  • L'évaluation d'une stratégie (Policy Evaluation)
  • L'amélioration d'une stratégue (Policy Improvement)

• L'algorithme par itération des valeurs (Values Iteration).

5. Algorithme par itération des stratégies

4.3. Amélioration d'une stratégie

La raison pour laquelle nous avons précédemment calculé la fonction des valeurs des états d'une stratégie avec l'algorithme itératif d'évaluation des stratégies est pour nous aider à trouver une meilleure stratégie.

Supposons que nous avons trouvé une fonction des valeurs d'états $V_\pi$ pour une stratégie arbitraire $\pi$. Pour certains états $s$ nous aimerions savoir s'il est préférable de changer ou de garder cette stratégie, c'est-à-dire de choisir une action $a\ne\pi(s)$. Nous savons quantifier de combien il est bon de garder cette action pour l'état $s$ lorsque l'agent suit la stratégie $\pi$ grâce à la valeur $V_\pi(s)$... Mais peut-être est-ce préférable de changer de stratégie ?

Une solution pour répondre à cette question est de sélectionner une nouvelle action $a'$ lorsque l'agent se trouve sur l'état $s$ et de poursuivre ensuite la stratégie initiale $\pi$.

La valeur d'action est alors la suivante:

$${q_\pi }\left( {s,a'} \right) = \sum\limits_{s',r} {p\left( {s',r|s,a'} \right)\left[ {r + \gamma {V_\pi }\left( {s'} \right)} \right]}$$

Il suffit ensuite de comparer cette valeur avec $V_\pi(s)$. Si la valeur d'action ${q_\pi }\left( {s,a'} \right)$ est supérieure - c'est-à-dire qu'il est plus efficace de sélectionner l'action $a'$ plutôt que l'action $\pi(s)$ et de poursuivre avec la stratégie $\pi$ - alors on peut estimer qu'il est préférable de choisir $a'$ à chaque fois que l'agent se trouve sur l'état $s$, et donc que la nouvelle stratégie est meilleure (il existe un théorème appelé le théorème d'amélioration des stratégies - policy impovement theorem - qui montre que cela est bien le cas).

Cette idée peut être étendue à l'ensemble de l'environnement et donc à toutes les actions possibles sur chaque état de celui-ci. Cela amène donc à la création d'une nouvelle stratégie $\pi'$ donnée par:

$$\begin{array}{l} \pi '\left( s \right) = \mathop {\arg \max }\limits_{a'} {\rm{ }}{q_\pi }\left( {s,a'} \right)\\ {\rm{ }} \quad\quad\:\:= \mathop {\arg \max }\limits_{a'} {\rm{ }}\sum\limits_{s',r} {p\left( {s',r|s,a'} \right)\left[ {r + \gamma {V_\pi }\left( {s'} \right)} \right]} \end{array}$$

La stratégie optimale prend l'action qui semble la meilleure au court terme (à partir de l'état suivant) selon la valeur donnée par $V_\pi$. C'est le processus d'amélioration des stratégies.

Supposons maintenant que cette nouvelle stratégie $\pi'$ est au moins aussi bien (mais non meilleure) que la stratégie initiale $\pi$. Alors $V_\pi=V_\pi'$ et de l'équation précédente il vient:

$${V_{\pi '}}\left( s \right) = \mathop {\max }\limits_{a'} \sum\limits_{s',r} {p\left( {s',r|s,a'} \right)\left[ {r + \gamma {V_\pi }\left( {s'} \right)} \right]}$$

C'est exactement l'équation d'optimalité de la fonction des valeurs d'états de Bellman. On peut donc conclure que dans ce cas $V_\pi' = V_\pi^*$ et que la stratégie $\pi'$ est une stratégie optimale.

Exemple

La colonne de droite représente un exemple d'amélioration de stratégies aléatoires. Dans cet exemple, la stratégie originale $\pi$ sélectionne les actions de manière équiprobable et la nouvelle stratégie $\pi'$ sélectionne les meilleures actions (greedy) par rapport à $V_\pi$. Les fonctions des valeurs des états sont données à gauche et l'ensemble des stratégies possibles $\pi'$ sont données à droite.

Les états avec de multiples flèches sur la stratégie $\pi'$ sont ceux sur lesquels plusieurs actions optimales sont possibles.

Le principe de l'algorithme est donc d'itérer chaque état $s$ de l'environnement et de trouver l'action $a$ sur cet état qui permet d'obtenir la meilleure valeur d'action en poursuivant la stratégie originale $\pi$. Si l'action est différente de celle utilisée dans la stratégie initiale, alors une nouvelle stratégie est mise en place grâce à cette nouvelle action. Cette recherche est répétée tant que des actions plus optimales sont découvertes.